package com.leetcode.www;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:给你一个由 n 个整数组成的数组nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
 *
 * 0 <= a, b, c, d< n
 * a、b、c 和 d 互不相同
 * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/4sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-04-04
 * Time:21:33
 */
public class DFS18 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Set<List<Integer>> set = new HashSet<>();
        Arrays.sort(nums);
        DFS(ret,list,0,target,nums,0);
        return ret;
    }
    public void DFS(List<List<Integer>> ret,List<Integer> list,int index,int target,int[] nums,int sum){
        if(list.size() == 4){
            if(sum == target){
                ret.add(new ArrayList(list));
            }
            return;
        }
        for(int i = index;i < nums.length;i ++){
            if(i > index && nums[i] == nums[i -1]){//去重保证不会出现换个顺序就是新结果的情况
                continue;
            }
            list.add(nums[i]);
            DFS(ret,list,i + 1,target,nums,sum + nums[i]);
            list.remove(list.size() - 1);
        }
    }
}
